package leetcode;

import java.util.*;

/**
 * ClassName: DataStructureOfHashMap
 * Package: leetcode
 * Description:
 * 一般哈希表都是用来快速判断一个元素是否出现集合里。
 *
 * @Author wjn
 * @Create 2025/5/28 14:44
 * @Version 1.0
 */
public class DataStructureOfHashMap {
    /**
     * 242. 有效的字母异位词
     * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
     * 示例 1:
     * 输入: s = "anagram", t = "nagaram"
     * 输出: true
     * 示例 2:
     * 输入: s = "rat", t = "car"
     * 输出: false
     *
     * @param s
     * @param t
     * @return
     **/
    public boolean isAnagram(String s, String t) {
        //  创建一个长度为26的数组，记录s中每个字母出现的次数
        int[] hash = new int[26];
        // 遍历s，将s中每个字母出现的次数记录在hash数组中
        for (int i = 0; i < s.length(); i++) {
            hash[s.charAt(i) - 'a']++;
        }
        // 遍历t，将t中每个字母出现的次数记录在hash数组中
        for (int i = 0; i < t.length(); i++) {
            hash[t.charAt(i) - 'a']--;
        }
        // 判断hash数组中的每个元素是否为0，如果为0，则说明s和t中的字母出现的次数相同，否则返回false
        for (int i = 0; i < hash.length; i++) {
            if (hash[i] != 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 349. 两个数组的交集
     * 给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
     *
     * @param nums1
     * @param nums2
     * @return
     **/
    public int[] intersection(int[] nums1, int[] nums2) {
        //  判断nums1和nums2是否为空
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        //  创建两个集合，分别存储结果和nums1中的元素
        Set<Integer> resultSet = new HashSet<>();
        Set<Integer> set1 = new HashSet<>();
        //  将nums1中的元素添加到set1中
        for (int i = 0; i < nums1.length; i++) {
            set1.add(nums1[i]);
        }
        //  遍历nums2，判断nums2中的元素是否在set1中，如果是，则添加到结果集合中
        for (int i = 0; i < nums2.length; i++) {
            if (set1.contains(nums2[i])) {
                //  将nums2中的元素添加到结果集合中,自动有去重的操作（set特性）
                resultSet.add(nums2[i]);
            }
        }
        // 将结果集合中的元素转换为数组并返回
        int[] result = new int[resultSet.size()];
        int i = 0;
        for (Integer num : resultSet) {
            result[i++] = num;
        }
        return result;
    }

    /**
     * 202. 快乐数
     * 编写一个算法来判断一个数 n 是不是快乐数。
     * 「快乐数」定义为：
     * 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
     * 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
     * 如果这个过程 结果为1，那么这个数就是快乐数。
     * 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
     *
     * @param n
     * @return
     **/
    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        while (n != 1 && !record.contains(n)) {
            record.add(n);
            n = getNextNum(n);
        }
        return n == 1;
    }

    private int getNextNum(int n) {
        int totalSum = 0;
        while (n > 0) {
            int temp = n % 10;
            totalSum += temp * temp;
            n /= 10;
        }
        return totalSum;
    }

    /**
     * 两数之和(使用map集合)
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        // 创建一个Map集合，用来存储遍历过的nums中的元素和索引
        Map<Integer, Integer> map = new HashMap<>();
        //  遍历nums数组
        for (int i = 0; i < nums.length; i++) {
            //  计算目标值
            int s = target - nums[i];
            //  判断map集合中是否存在目标值
            if (map.containsKey(s)) {
                //  如果存在，则返回索引
                return new int[]{map.get(s), i};
            } else {
                // 如果不存在，则将当前元素和索引添加到map集合中
                map.put(nums[i], i);
            }
        }
        return null;
    }

    /**
     * 四数相加 II
     *
     * @param nums1
     * @param nums2
     * @param nums3
     * @param nums4
     * @return
     */
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        // 创建一个Map集合，用来存储nums1和nums2中的元素之和以及相同和的个数
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                int sum = nums1[i] + nums2[j];
                //  map集合中不存在sum，则将sum添加到map集合中，若存在，则将sum的个数加1
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }

        int count = 0;
        for (int i = 0; i < nums3.length; i++) {
            for (int j = 0; j < nums4.length; j++) {
                int sum = nums3[i] + nums4[j];
                //  map集合中存在-sum，则将-sum的个数加到count中
                if (map.containsKey(-sum)) {
                    // count += map.get(-sum);
                    count += map.get(-sum);
                }
            }
        }
        return count;
    }

    /**
     * 赎金信
     *
     * @param ransomNote
     * @param magazine
     * @return
     */
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        int[] hash = new int[26];
        for (int magazineChar : magazine.toCharArray()) {
            hash[magazineChar - 'a'] += 1;
        }
        for (int ransomNoteChar : ransomNote.toCharArray()) {
            hash[ransomNoteChar - 'a'] -= 1;
        }
        // 如果数组中存在负数，说明ransomNote字符串中存在magazine中没有的字符
        for (int i = 0; i < hash.length; i++) {
            if (hash[i] < 0) {
                return false;
            }
        }
        return true;
    }


    /**
     * 三数之和
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.length; i++) {
            //剪枝
            if (nums[i] > 0) {
                return result;
            }
            // 去重a
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                    while (right > left && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    while (right > left && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    right--;
                    left++;
                }
            }
        }
        return result;
    }

    /**
     * 四数之和（完成）
     *
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int k = 0; k < nums.length; k++) {
            if (nums[k] > 0 && nums[k] > target) {
                return result;
            }
            // 对nums[k]去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.length; i++) {
                // 第二级剪枝
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;    // 注意是break到上一级for循环，如果直接return result;会有遗漏
                }
                // 对nums[i]去重
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.length - 1;
                while (right > left) {
                    long sum = (long) nums[k] + nums[i] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        while (right > left && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        right--;
                        left++;
                    }
                }
            }
        }
        return result;
    }
}
